{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DoublyLinkedBase(object):\n",
    "    class _Node(object):\n",
    "        __slots__ = '_elem', '_prev', '_next'\n",
    "        def __init__(self, elem, prev, next):\n",
    "            self._elem = elem\n",
    "            self._prev = prev \n",
    "            self._next = next \n",
    "            \n",
    "    def __init__(self):\n",
    "        self._header=self._Node(None,None,None)\n",
    "        self._trailer=self._Node(None,None,None)\n",
    "        self._header._next=self._trailer\n",
    "        self._trailer._prev=self._header\n",
    "        self._size=0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self._size\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size==0\n",
    "    \n",
    "    def insert_between(self,e,pred,succ):\n",
    "        \"\"\"\n",
    "        Add an element between two existing nodes\n",
    "        \"\"\"\n",
    "        new = self._Node(e,pred,succ)\n",
    "        pred._next=new\n",
    "        succ._prev=new\n",
    "        self._size+=1\n",
    "        return new\n",
    "    \n",
    "    def delete(self,node):\n",
    "        \"\"\"\n",
    "        Delete a node from the list\n",
    "        \"\"\"\n",
    "        pred=node._prev\n",
    "        succ=node._next\n",
    "        pred._next=succ\n",
    "        succ._prev=pred\n",
    "        self._size-=1\n",
    "        elem=node._elem\n",
    "        node._prev=node._next=node._elem=None\n",
    "        return elem\n",
    "    \n",
    "\n",
    "class Deque(DoublyLinkedBase):\n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty(\"Deque is empty\")\n",
    "        return self._header._next._elem\n",
    "    \n",
    "    def last(self):\n",
    "        if self.is_empty():\n",
    "            raise Empty(\"Deque is empty\")\n",
    "        return self._trailer._prev._elem\n",
    "    \n",
    "    def insert_first(self,e):\n",
    "        return self.insert_between(e,self._header,self._header._next)\n",
    "    \n",
    "    def insert_last(self,e):\n",
    "        return self.insert_between(e,self._trailer._prev,self._trailer)\n",
    "    \n",
    "    def delete_first(self):\n",
    "        return self.delete(self._header._next)\n",
    "    \n",
    "    def delete_last(self):\n",
    "        return self.delete(self._trailer._prev)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        L=[]\n",
    "        if self.is_empty():\n",
    "            return f'{L}'\n",
    "        else:\n",
    "            current =self._header._next\n",
    "            while current is not self._trailer:\n",
    "                L.append(current._elem)\n",
    "                current = current._next\n",
    "            return f'{L}'\n",
    "\"\"\"       \n",
    "if __name__=='__main__':\n",
    "    d=Deque()\n",
    "    \n",
    "    d.insert_first(1)\n",
    "    d.insert_first(2)\n",
    "    d.insert_last('aaa')\n",
    "    d.insert_last('bbb')\n",
    "    print(d)\n",
    "    d.delete_first()\n",
    "    d.delete_last()\n",
    "    print(d)\n",
    "\"\"\" \n",
    "#from DoublyLinkedBase import DoublyLinkedBase\n",
    "#from empty import Empty\n",
    "class PositionalList(DoublyLinkedBase): \n",
    "    class Position: \n",
    "        def __init__(self, container, node):\n",
    "            self._container = container\n",
    "            self._node = node\n",
    "            \n",
    "        def element(self):\n",
    "            return self._node._elem\n",
    "    \n",
    "        def __eq__(self, other):\n",
    "            return type(other)is type(self) and other._node is self._node \n",
    "    \n",
    "        def __ne__(self, other):\n",
    "            return not (self == other)\n",
    "\n",
    "    def _validate(self, p):\n",
    "        if not isinstance(p, self.Position):\n",
    "            raise TypeError('p must be proper Position type')\n",
    "        if p._container is not self:\n",
    "            raise ValueError('p does not belong to this container')\n",
    "        if p._node._next is None:\n",
    "            raise ValueError('p is no longer valid')\n",
    "        return p._node\n",
    "    \n",
    "    def _make_position(self, node):\n",
    "        if node is self._header or node is self._trailer:\n",
    "            return None \n",
    "        else:\n",
    "            return self.Position(self, node)\n",
    "\n",
    "    def first(self):\n",
    "        return self._make_position(self._header._next)\n",
    "    \n",
    "    def last(self):\n",
    "        return self._make_position(self._trailer._prev)\n",
    "    \n",
    "    def before(self, p):\n",
    "        node = self._validate(p)\n",
    "        return self._make_position(node._prev)\n",
    "    \n",
    "    def after(self, p):\n",
    "        node = self._validate(p)\n",
    "        return self._make_position(node._next)\n",
    "    \n",
    "    def __iter__(self):\n",
    "        cursor = self.first()\n",
    "        while cursor is not None:\n",
    "            yield cursor.element()\n",
    "            cursor = self.after(cursor)\n",
    "            \n",
    "    def _insert_between(self, e, predecessor, successor):\n",
    "        node = super()._insert_between(e, predecessor, successor)\n",
    "        return self._make_position(node)\n",
    "\n",
    "    def add_first(self, e):\n",
    "        return self._insert_between(e, self._header, self._header._next)\n",
    "    \n",
    "    def add_last(self, e):\n",
    "        return self._insert_between(e, self._trailer ._prev, self._trailer)\n",
    "    \n",
    "    def add_before(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        return self._insert_between(e, original. _prev, original)\n",
    "    \n",
    "    def add_after(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        return self._insert_between(e, original, original._next)\n",
    "\n",
    "    def delete(self, p):\n",
    "        original = self._validate(p)\n",
    "        return self._delete_node(original)\n",
    "    \n",
    "    def replace(self, p, e):\n",
    "        original = self._validate(p)\n",
    "        old_value = original._element\n",
    "        original._element = e\n",
    "        return old_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
